//盈利计划（hard）: https://leetcode.cn/problems/profitable-schemes/
class Solution {
public:
	int profitableSchemes(int n, int m, vector<int>& g, vector<int>& p)
	{
		const int MOD = 1e9 + 7; // 注意结果取模
	
			int len = g.size();
		vector<vector<int>> dp(n + 1, vector<int>(m + 1));
		for (int j = 0; j <= n; j++) dp[j][0] = 1; // 初始化
		for (int i = 1; i <= len; i++)
		{
			for (int j = n; j >= g[i - 1]; j--) // 记得修改遍历顺序
			{
				for (int k = m; k >= 0; k--) // 注意修改顺序
				{
					dp[j][k] += dp[j - g[i - 1]][max(0, k - p[i - 1])];
					dp[j][k] %= MOD; // 注意结果取模
				}
			}
				
		}
			
		return dp[n][m];
	}
};